import java.util.*;

class PeekingIterator implements Iterator<Integer> {
    Iterator<Integer> iterator;
    Integer next;
    public PeekingIterator(Iterator<Integer> iterator) {
        // initialize any member here.
        this.iterator=iterator;
        next=iterator.next();
    }

    // Returns the next element in the iteration without advancing the iterator.
    public Integer peek() {
        return next;
    }

    // hasNext() and next() should behave the same as in the Iterator interface.
    // Override them if needed.
    @Override
    public Integer next() {
        Integer ret=next;
        next=iterator.hasNext()?iterator.next():null;
        return ret;
    }

    @Override
    public boolean hasNext() {
        return next!=null;
    }
}













class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}


public class project {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue=new ArrayDeque<>();
        int ret=0;
        if(root!=null){
            queue.add(root);
            while (!queue.isEmpty()){
                int size=queue.size();
                for(int i=0;i<size;i++){
                    TreeNode tmp=queue.poll();
                    if(i==0){
                        ret=tmp.val;
                    }
                    if(tmp.left!=null){
                        queue.add(tmp.left);
                    }
                    if(tmp.right!=null){
                        queue.add(tmp.right);
                    }
                }
            }
        }
        return ret;
    }

















    public List<List<Integer>> combinationSum3(int k, int n) {
    List<List<Integer>> list=new ArrayList<>();
    Deque<Integer> deque=new ArrayDeque<>();
    dfs(1,9,k,n,deque,list);
    return list;
}
    public void dfs(int start,int end,int size,int sum,Deque<Integer> deque,List<List<Integer>> list){
        if(sum==0&&deque.size()==size){
            list.add(new ArrayList<>(deque));
        }
        for(int i=start;i<=end;i++){
            deque.addLast(i);
            dfs(i+1,end,size,sum-i,deque,list);
            deque.removeLast();
        }
    }


















    int ret=0;
    public int numTilePossibilities(String tiles) {
        int[] arr=new int[26];
        for(char ch : tiles.toCharArray()){
            arr[ch-'A']++;
        }
        dfs1(arr);
        return ret;
    }
    public void dfs1(int[] arr){
        for(int i=0;i<26;i++){
            if(arr[i]==0){
                continue;
            }
            arr[i]--;
            ret++;
            dfs1(arr);
            arr[i]++;
        }
    }












    public int numOfPairs(String[] nums, String target) {
        int len=nums.length;
        int sum=0;
        for(int i=0;i<len;i++){
            for(int j=0;j<len;j++){
                if(i!=j){
                    String str = nums[i] + nums[j];
                    if(str.equals(target)){
                        sum++;
                    }
                }
            }
        }
        return sum;
    }
















    public int[] memLeak(int memory1, int memory2) {
        int[] arr=new int[3];
        int index=1;
        while (true){
            if(index<=Math.max(memory1,memory2)){
                if (memory1 == memory2) {
                    memory1-=index;
                } else if (memory1 > memory2) {
                    memory1-=index;
                } else if (memory2 > memory1) {
                    memory2-=index;
                }
                index++;
            }else{
                break;
            }
        }
        arr[0]=index;
        arr[1]=memory1;
        arr[2]=memory2;
        return arr;
    }
















    public static void main(String[] args) {
        int n=3;
        int[] arr={0,1};
        String s="RRDDLU";
        int[] ret=executeInstructions(n,arr,s);
        for(int i : ret){
            System.out.print(i+" ");
        }
    }
    public int[][] diagonalSort(int[][] mat) {
        int row=mat.length;
        int col=mat[0].length;
        for(int i=0;i<col;i++){
            swap(mat,0,i,row,col);
        }
        for(int i=1;i<row;i++){
            swap(mat,i,0,row,col);
        }
        return  mat;
    }
    public void swap(int[][] arr,int i,int j,int row,int col){
        int tmp=0;
        for(;i<row-1&&j<col-1;i++,j++){
            for(int k=i+1,p=j+1;k<row&&p<col;k++,p++){
                if(arr[i][j]>arr[k][p]){
                    tmp = arr[i][j];
                    arr[i][j] = arr[k][p];
                    arr[k][p] = tmp;
                }
            }
        }
    }






    public boolean isSameAfterReversals(int num) {
        if(num==0){
            return true;
        }
        return num%10!=0;
    }
















    public static int[] executeInstructions(int n, int[] startPos, String s) {
        int len=s.length();
        int x=0;
        int y=0;
        int[] arr=new int[len];
        int sum=0;
        for(int i=0;i<len;i++){
            sum=0;
            x=startPos[0];
            y=startPos[1];
            for(int j=i;j<len;j++){
                char ch=s.charAt(j);
                switch(ch){
                    case 'U':
                        x--;
                        break;
                    case 'D':
                        x++;
                        break;
                    case 'L':
                        y--;
                        break;
                    case 'R':
                        y++;
                        break;
                }
                if(x>=0&&x<n&&y>=0&&y<n){
                    sum++;
                }else{
                    break;
                }
            }
            arr[i]=sum;
        }
        return arr;
    }















    public int numFriendRequests(int[] ages) {
        int len=ages.length;
        int sum=0;
        Arrays.sort(ages);
        int left=0;
        int right=0;
        for(int age : ages){
            if(age<15){
                continue;
            }
            while (ages[left]<=0.5*age+7){
                left++;
            }
            while (right+1<len&&ages[right+1]<=age){
                right++;
            }
            sum+=right-left;
        }
        return sum;
    }
}
